package com.jack.leetcode.动态规划;

/*** 
 * @author zhangjie
 * @date 2020/4/22 21:30
 */
public class 爬楼梯70 {

    public int climbStairs(int n) {
        if(n == 1){
            return 1;
        }
        if(n == 2){
            return 2;
        }
        int[] a = new int[n+1];
        a[1] = 1;
        a[2] = 2;
        for(int i = 3;i<=n;i++){
            a[i] = a[i-1] + a[i-2];
        }
        return a[n];
    }

    private int dynamic(int n){
        if(n == 1){
            return 1;
        }
        if(n == 2){
            return 2;
        }
        return dynamic(n-1)+dynamic(n-2);
    }
}
